package main

import "fmt"

/*
给你一个 互不相同 的整数数组，其中 locations[i] 表示第 i 个城市的位置。同时给你 start，finish 和 fuel 分别表示出发城市、目的地城市和你初始拥有的汽油总量

每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足  j != i 且 0 <= j < locations.length ，并移动到城市 j 。从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。

请注意， fuel 任何时刻都 不能 为负，且你 可以 经过任意城市超过一次（包括 start 和 finish ）。

请你返回从 start 到 finish 所有可能路径的数目。

由于答案可能很大， 请将它对 10^9 + 7 取余后返回。

作者：宫水三叶
链接：https://leetcode-cn.com/leetbook/read/path-problems-in-dynamic-programming/r8pzo1/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

type data struct {
	idx      int
	leftFuel int
}

// bfs算法，如果面对比较大的数据，会内存溢出
func countRoutes(locations []int, start int, finish int, fuel int) int {
	var queue []data
	queue = append(queue, data{idx: start, leftFuel: fuel})
	var cnt int
	for len(queue) != 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			headData := queue[0]
			headIdx := headData.idx
			leftFuel := headData.leftFuel
			queue = queue[1:]
			// fmt.Println(headData)
			if headIdx == finish {
				cnt++
				// break	// 这里不break，因为题目允许来回重复走动，所以如果还有燃料的情况下，可以继续
			}
			for j := 0; j < len(locations); j++ {
				if j == headIdx {
					continue
				}
				needFuel := 0
				if locations[j] > locations[headIdx] {
					needFuel = locations[j] - locations[headIdx]
				} else {
					needFuel = locations[headIdx] - locations[j]
				}
				if leftFuel >= needFuel {
					queue = append(queue, data{idx: j, leftFuel: leftFuel - needFuel})
				}
			}
		}
	}
	return cnt
}

func countRoutesDP(locations []int, start int, finish int, fuel int) int {
	var dp [][]int
	for i := 0; i < len(locations); i++ {
		dp = append(dp, make([]int, fuel+1))
	}
	dp[finish][0] = 1
	for i := 0; i < len(dp[finish]); i++ {
		dp[finish][i] = 1
	}
	for i := 0; i < len(dp); i++ {
		for j := 0; j < len(dp[i]); j++ {
			for next := 0; next < len(dp); next++ {
				if next == i {
					continue
				}
				var needFule int
				if locations[i] < locations[next] {
					needFule = locations[next] - locations[i]
				} else {
					needFule = locations[i] - locations[next]
				}
				if needFule <= j {
					dp[i][j] += dp[next][j-needFule]
				}
			}
		}
	}
	for i := 0; i < len(dp); i++ {
		fmt.Println(dp[i])
	}
	return dp[start][fuel]
}

func main() {
	// locations := []int{2, 3, 6, 8, 4}
	// start := 1
	// finish := 3
	// fuel := 5
	// locations := []int{5, 2, 1}
	// start := 0
	// finish := 2
	// fuel := 3
	locations := []int{4, 3, 1}
	start := 1
	finish := 0
	fuel := 6
	fmt.Println(countRoutesDP(locations, start, finish, fuel))
}
